1. Technical Field
The present invention is generally directed to the field of data communications, and more specifically to data communication system utilising automatic repeat request (ARQ) systems and protocols, and to hybrid ARQ (HARQ).
2. Description of the Related Art
The past decade has seen an explosion in the development and deployment of communications systems. Advances in network, wireless and fiber-optic technologies have revolutionized modern communications. Even some of the most sophisticated communications technologies have achieved levels of cost and ease of use facilitating widespread accessibility.
Communications systems are typically designed with the goal of maximizing performance given such system constraints as power, bandwidth and data rate. There are many quantitative measures of system performance, the most relevant measure depending on the nature of the particular system. In general, systems can broadly be divided into two categories, those with and those without feedback channels. In a system with a single transmitter and a single receiver, the presence of a feedback channel allows the receiver to send information back to the transmitter pertaining to the success or failure of the transmission. Applications which have feedback channels are typically delay insensitive.
In systems without a feedback channel, the performance may for example be defined by the bit error rate (BER). The BER is the probability that a transmitted bit will be decoded erroneously by the receiver. In any digital communications system, the BER decreases and performance improves with higher transmitted signal power. However, given power constraints, a desirable goal is to improve BER performance without increasing power requirements, or alternately, to achieve a given BER with less power. Particularly in wireless, mobile, and other battery-powered or limited-power communication systems and devices, power consumption is a primary concern.
Forward error correction (FEC) is a known technique for improving BER without increasing power or achieving a desired BER with less power. FEC involves adding controlled redundancy to source or transmitted data in a manner that allows a receiver to detect and correct errors that occur on a transmission channel. This increases the immunity of the transmitted signal to noise without increasing signal power.
When a feedback channel is available, automatic repeat request (ARQ) schemes can be implemented. ARQ schemes typically operate with frames of information data. The frames consist of information bits and error-detecting cyclic redundancy check (CRC) bits, implemented with a cyclic code. A receiver uses the CRC bits to determine if any bit errors have occurred and, if so, requests a retransmission of the frame by sending a negative acknowledgment (NAK; i.e., an error indication) on the feedback channel. This is repeated until the frame is received without errors, in which case a positive acknowledgment (ACK) is sent. The BER of ARQ schemes is determined by the undetected error rate of the error detecting code and is usually selected to be very low, effectively zero. The BER is therefore inappropriate as a measure of ARQ system performance. Instead, throughput, defined as the average number of encoded data bits accepted by the receiver in the time it takes the transmitter to send a single bit, is used to measure performance. Throughput can be viewed as a measure of the retransmission overhead of the ARQ scheme. Throughput is measured in bits/channel use and is upper-bounded by the channel capacity.
Hybrid ARQ (HARQ) systems combine FEC and ARQ in order to improve ARQ throughput performance. In pure ARQ systems, the probability of a frame being in error is a function of channel bit error rate and frame length. The redundant bits generated by a FEC code, also known as parity bits, are incorporated into the frame based retransmission approach of ARQ systems. By incorporating FEC, the frame error rate (FER), which is a measure similar to BER described above but based on frames instead of bits, can be reduced significantly. This accordingly reduces the number of retransmissions required and therefore improves throughput performance, but requires more complex transmitter and receiver designs to provide for FEC.
Early HARQ systems simply add FEC redundancy to every transmitted frame. The receiver then uses the decoding algorithm corresponding to the FEC scheme to estimate the bits of the frame. The CRC is then computed to determine of the received frame contains errors and if so, retransmission of the frame may be requested. In the event of a retransmission request, the process is repeated. This limits the throughput to a maximum value equal to the rate of the FEC code used. For example, if a rate ½ code is used, the maximum throughput is 0.5. Such a system is known as type-I HARQ system. In some cases, type-I HARQ systems use the same code for both error detection and error correction.
A more sophisticated approach is to use the idea of incremental redundancy. Systems using this approach are known as type-II HARQ systems and adaptively vary the amount of additional parity bits sent to the receiver. A type-II HARQ protocol operates to initially transmit only information bits and CRC bits. Subsequent retransmission requests entail incremental transmission of parity bits. Each parity increment is combined with the previously received symbols by a decoder in the receiver in order to decode the frame with a lower frame error rate (FER) than before. After each retransmission, the receiver is decoding a more powerful, lower rate code. It is essential that the FEC used in type-II HARQ systems is a rate compatible code. Rate compatibility ensures that when a family of different rate codes is generated by puncturing a single low rate code, the parity bits used in any member of the family includes all the parity bits used in all higher rate members of the family.
Type-II HARQ systems have the ability to vary their throughput dynamically as channel conditions change. This adaptability makes such systems particularly useful in applications with fluctuating channel conditions, such as mobile and satellite packet data, where a feedback channel is available and latency due to retransmission delay is acceptable.
There has been a great deal of previous work in the area of HARQ systems. However, most of this work has been based on codes less powerful than turbo or low density parity check (LDPC) codes. Such systems have been developed using Bose-Chaudhuri-Hochquenghem (BCH) codes, half-rate invertible codes, rate ½ convolutional codes and complementary convolutional codes. However, the throughput of such known systems does not approach the limit of channel capacity.
One known turbo code based HARQ system is described in K. R. Narayanan and G. L. Stüber, “A Novel ARQ Technique Using the Turbo Coding Principle”, IEEE Commun. Letters, vol. 1, pp. 49-51, March 1997. In this system, a rate ½ turbo encoder is used. The systematic and parity bits from the encoder are sent in the initial transmission. In response to a NAK, the systematic data is interleaved with a different interleaver from the one used in the turbo encoder and is then encoded with the same rate ½ turbo encoder that was used for the initial transmission. The systematic and parity bits from this encoding are then sent. This is repeated with each NAK with a different interleaver used each time. The decoder is similar to a standard turbo decoder except that the results of a previous frame's decoding are used as the initial extrinsic information in the next frame's decoding. As will become apparent from the detailed description of the present invention below, this scheme is different from the present invention, such as, for example that all parity bits are transmitted in every transmitted and retransmitted frame.
A known type-I HARQ system using a rate ½ turbo code is described in J. Hámorský, U. Wachsmann, J. B. Huber and A. {hacek over (C)}i{hacek over (z)}már, “Hybrid Automatic Repeat Request Scheme with Turbo Codes”, Proc. of International Symposium on Turbo Codes and Related Topics, Brest, France, September 1997. Here, every transmitted frame includes the parity bits from a rate ½ turbo code, in addition to the information bits. This scheme has a maximum throughput of only 0.5.
A further known HARQ scheme disclosed for example in D. N. Rowitch and L. B. Milstein, “Rate Compatible Punctured Turbo (RCPT) Codes in a Hybrid FEC/ARQ System”, Proc. IEEE GLOBECOM '97, Phoenix, Ariz., November 1997, is restricted to only certain particular code rates and requires more complex encoding and decoding arrangements relative to those in accordance with aspects of the instant invention.
These previous approaches lack, for example, a HARQ system and method having improved throughput approaching channel capacity. These previous approaches also lack a HARQ scheme which provides for arbitrary code rates without requiring more complex encoding and decoding arrangements. For example, R. Mantha, A. Hunt and S. Crozier, “An Efficient Software Implementation of a Variable Rate Modem”, Proc. 4th International Mobile Satellite Conferences, Ottawa, ON, Canada, June 1995, pp. 8-12, disclosed an approach that is significantly different from the present invention in that it related to a variable rate modem, not to puncturing in a HARQ system.